Each rule of a packet forwarding table comprises a prefix and a next hop. Packet forwarding is done by determining the next hop associated with the longest prefix in the forwarding table that matches the destination address of the packet to be forwarded. Several solutions for very high-speed longest prefix matching have been proposed for surveys (see the reference M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, Survey and taxonomy of IP address lookup algorithms, IEEE Network, 2001, 8-23, (the teachings of which are hereby incorporated by reference in their entirety and hereinafter referred to as “Ruiz”) and the reference S. Sahni, K. Kim, and H. Lu, Data structures for one-dimensional packet classification using most-specific-rule matching, International Journal on Foundations of Computer Science, 14, 3, 2003, 337-358, (the teachings of which are hereby incorporated by reference in their entirety and hereinafter referred to as “Sahni8”). Among the many proposed solutions to the packet forwarding problem, those employing TCAMs are the simplest and fastest. A TCAM is a fully associative memory in which each bit may be in one of 3 states—0, 1 and don't care. By loading the forwarding table prefixes into the TCAM in decreasing order of prefix length (ties are broken arbitrarily), the TCAM index of the longest matching prefix for any destination address may be determined in one TCAM cycle. Using this index, the word of SRAM can be accessed where the next hop associated with the matching prefix is stored and complete the forwarding task. So, the simplest TCAM solution to packet forwarding requires 1 TCAM search and 1 SRAM access to forward a packet. Two drawbacks of this TCAM solution are (a) an IPV4 forwarding table with n prefixes requires a TCAM that has 32n bits and (b) since each lookup searches the entire 32n-bit TCAM, the power consumption is that for a TCAM of this size.
The reference F. Zane, G. Narlikar and A. Basu, CoolCAMs: Power-Efficient TCAMs for Forwarding Engines, INFOCOM, 2003, (the teachings of which is hereby incorporated by reference in its entirety and hereinafter referred to as “Zane”) Several strategies—e.g., the reference R. Panigrahy and S. Sharma, Reducing TCAM power consumption and increasing throughput, IEEE Symposium on High Performance Interconnects Hot Interconnects, 2002 (the teachings of which are hereby incorporated by reference in their entirety, (hereinafter referred to as “Panigrahy”), the reference Zane, the reference K. Zheng, C. Hu, H. Liu, and B. Liu, An ultra high throughput and power efficient TCAM-based IP lookup engine, IEEE INFOCOM, 2004 (the teachings of which are hereby incorporate by reference in their entirety and hereinafter referred to as “Zheng”), the reference H. Lu, Improved Trie Partitioning for Cooler TCAMs, IASTED International Conference on Advances in Computer Science and Technology, 2004 (the teachings of which is hereby incorporated by reference in its entirety and herein after referred to as “HaLu”)—have been proposed to reduce TCAM power significantly by capitalizing on a feature in contemporary TCAMs that permits one to select a portion of the entire TCAM for search. The power consumption now corresponds to that for a TCAM whose size is that of the portion that is searched. Using the example of the reference Zane, suppose in this example there is a TCAM with a capacity of 512K prefixes and that the TCAM has a block size of 6K. So, the total number of blocks is 64. The portion of the total TCAM that is to be searched is specified using a 64-bit vector. Each bit of this vector corresponds to a block. The 1s in this vector define the portion (subtable) of the TCAM that is to be searched and the power required to search a TCAM subtable is proportional to the subtable size. While it is not required that a subtable be comprised of contiguous TCAM blocks, in this example embodiment of the present invention the TCAM blocks are contiguous. The term bucket is used to refer to a set of contiguous blocks. Although, in the example of the reference Zane the size of a bucket is a multiple of 8K prefixes, it is important to note that bucket sizes are required only to be integer.
The reference Zane partition the forwarding table into smaller subtables (actually, buckets) so that each lookup requires 2 searches of smaller TCAMs. Their method, however, increases the total TCAM memory that is required. Halu has proposed an improved table partitioning algorithm for TCAMs. In the reference by M. Akhbarizadeh, M. Nourani, R. Panigrahy and S. Sharma, A TCAM-based parallel architecture for high-speed packet forwarding, IEEE Trans. on Computers, 56, 1, 2007, 58-2007 (the teachings of which are hereby incorporated by reference in its entirety, hereinafter referred to as “Akbar”) proposes an alternative TCAM architecture that employs multiple TCAMs and multiple TCAM selectors. The routing table is distributed over the multiple TCAMs, the selectors decide which TCAM is to be searched. The architecture of Akhbar is able to determine the next-hop for several packets in parallel and so achieves processing rates higher than those achievable by using a single pipeline architecture such as the one proposed by the reference Zane. The proposal of the reference Zane, however, has the advantage that it can be implemented a commercial network processor board equipped with a TCAM and an SRAM (for example, Intel's IXP 3000 network processor supports a TCAM and up to 4 SRAMs, no customized hardware support is required) whereas that of Akhbar cannot.
According what is needed is a method and system to over come the problems encountered in the prior art and to optimize the displaying of the pictures at a selected speed according to the performance of the data stream processing chain, from the extracting of the data from the hard disk, up to display.